#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/11 21:45
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _39_combinationSum.py



from copy import deepcopy


class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        path = []
        
        def dfs(index, target):
            if target<0:
                return
            if target == 0:
                res.append(deepcopy(path))
                return
            
            for i in range(index, len(candidates)): # # 放入idnex只是为了保存顺序
                if target - candidates[i]<0:continue
                path.append(candidates[i])
                dfs(i, target-candidates[i])
                path.pop()
        
        dfs(0, target)
        return res
            

